package foundation.图论.最小生成树;

import java.util.*;

/**
 * <p>
 * {@code Prim} 算法（不算常用）
 * <p>
 * 用于生成最小生成树的算法，步骤如下：
 * <ol>
 *     <li>解锁的点的集合叫 set（普通集合）、解锁的边的集合叫 heap（小根堆）。set 和 heap 都为空。</li>
 *     <li>可从任意点开始，开始点加入到 set，开始点的所有边加入到 heap</li>
 *     <li>从 heap 中弹出权值最小的边 e，查看边 e 所去往的点 x
 *         <ul>
 *             <li>A. 如果 x 已经在 set 中，边 e 舍弃，重复步骤 3</li>
 *             <li>B. 如果 x 不在 set 中，边 e 属于最小生成树，把 x 加入 set，重复步骤 3</li>
 *         </ul>
 *     </li>
 *     <li>当 heap 为空，最小生成树也就得到了</li>
 * </ol>
 */
public class Prim {
    static int N = 10010;
    // 头指针数组
    static int[] h = new int[N];
    static int[] to = new int[N];
    static int[] next = new int[N];
    static int[] weight = new int[N];
    static int idx;
    static int n = 0, m = 0, select = 0, res = 0;

    public static void add(int u, int v, int w) {
        next[idx] = h[u];
        to[idx] = v;
        weight[idx] = w;
        h[u] = idx++;
    }


    public static boolean prim() {
        Set<Integer> set = new HashSet<>();
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        queue.add(new int[]{1, 0});
        while (!queue.isEmpty()) {
            int[] edge = queue.poll();
            int cur = edge[0];
            int w = edge[1];
            // 当前点不在集合中,就把它的所有连接的点都放入队列
            if (!set.contains(cur)) {
                set.add(cur);
                res += w;
                select++;
                for (int ei = h[cur]; ei > 0; ei = next[ei]) {
                    queue.add(new int[]{to[ei], weight[ei]});
                }
            }
        }
        // select 为选的点
        return select == n;
    }


    public static void init() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        idx = 1;
        Arrays.fill(h, 1, n + 1, 0);
        select = 0;
        res = 0;
        int u, v, w;
        for (int i = 0; i < m; i++) {
            u = sc.nextInt();
            v = sc.nextInt();
            w = sc.nextInt();
            add(u, v, w);
            add(v, u, w);
        }
    }


    public static void main(String[] args) {
        init();
        if (prim()) {
            System.out.println(res);
        } else {
            System.out.println("orz");
        }
    }
}
